#include "balanceBinarySearchTree.h"
#include "doubleLinkListQueue.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

/* 状态码 */
enum STATUS_CODE
{
    ON_SUCCESS,
    MALLOC_ERROR,
    NULL_PTR,
    INVALID_ACCESS,
};

/* 创建二叉搜索树的前置声明 */
static BalanceBinarySearchTreeNode *createBalanceBinarySearchTreeNode(ELEMENTTYPE data, BalanceBinarySearchTreeNode *parent);

/* 结点的度为2 */
static int BalanceBinarySearchTreeNodeTwoChildrens(BalanceBinarySearchTreeNode *node);

/* 结点的度为1 */
static int BalanceBinarySearchTreeNodeOneChildrens(BalanceBinarySearchTreeNode *node);

//前序遍历静态声明
static int BalanceBinarySearchTreeInnerPreOrder(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode *travelNode);

/* 指定删除结点 */
static BalanceBinarySearchTreeNode * baseAppointValGetBSTreeNode(BalanceBinarySearchTree *pTree, ELEMENTTYPE data);

/* 结点的度为0 (叶子结点) */
static int BalanceBinarySearchTreeNodeIsLeaf(BalanceBinarySearchTreeNode *node);

/* 结点的前驱结点 */
static BalanceBinarySearchTreeNode *BalanceBinarySearchTreeNodeGetPrecursor(BalanceBinarySearchTreeNode *node);

/* 结点的后继结点 */
static BalanceBinarySearchTreeNode *BalanceBinarySearchTreeNodeGetSuccessor(BalanceBinarySearchTreeNode *node);

static int BalanceBinarySearchTreeInnerPreOrder(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * travelNode);

/* 中序遍历 */
static int BalanceBinarySearchTreeInnerInOrder(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * travelNode);

/* 后序遍历 */
static int BalanceBinarySearchTreeInnerPostOrder(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * travelNode);

/* 根据指定的值获取对应的结点 */
static BalanceBinarySearchTreeNode * baseAppointValGetBSTreeNode(BalanceBinarySearchTree *pTree, ELEMENTTYPE data);

/* 删除指定的树节点*/
static int BalanceBinarySearchTreeDeleteNode(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * delNode);

/* 平衡二叉搜索树结点平衡因子(结点才有) */
static int BalanceBinarySearchTreeNodeFactor(BalanceBinarySearchTreeNode *node);

/* 判断是否平衡 */
static int BalanceBinarySearchTreeNodeIsBalance(BalanceBinarySearchTreeNode *node);

/* 更新高度 */
static int BalanceBinarySearchTreeNodeUpdataHeight(BalanceBinarySearchTreeNode *node);





/* 树的初始化 */
int BalanceBinarySearchTreeInit(BalanceBinarySearchTree **pTree, int (*compareFunc)(ELEMENTTYPE arg1, ELEMENTTYPE arg2), int (*printFunc)(ELEMENTTYPE arg))
{
    BalanceBinarySearchTree *tree = malloc(sizeof(BalanceBinarySearchTree) * 1);
    if (tree == NULL)
    {
        return MALLOC_ERROR;
    }

    /* 清除脏数据 */
    memset(tree, 0, sizeof(BalanceBinarySearchTree) * 1);

    /* 树的元素为0 */
    tree->size = 0;
    tree->height = 0;
    tree->root = NULL;

    /* 比较器 */
    tree->compareFunc = compareFunc;

    /* 打印器 */
    tree->printFunc = printFunc; //个人放置的打印器
  
    /* 二级指针解引用 */
    *pTree = tree;
    return ON_SUCCESS;
}

/* 结点的前驱结点 */
/* 前驱结点是：当前结点中序遍历（有序）的前面一个结点 */
static BalanceBinarySearchTreeNode  * BalanceBinarySearchTreeNodeGetPrecursor(BalanceBinarySearchTreeNode * node)
{
    
    BalanceBinarySearchTreeNode * travelNode = NULL;

    /* if( BalanceBinarySearchTreeNodeHasTwoChildrens(node)) */
    if(node->left != NULL)
    {
        travelNode = node->left;
        while(travelNode->right != NULL)
        {
            travelNode = travelNode->right;
        }
        return travelNode;
    }

    //程序到这，左子树一定为空
    //找前驱一定是找比他小的
    //只能够往上面（parent->parent->oarent走
    //如果是父节点的右边，则直接返回父节点
    //若果是父节点的左边，则一直往上跑，直到当前结点时父节点的右边
    /* 说明一定度不为2 */

    travelNode = node;
    while(travelNode->parent != NULL && travelNode== travelNode->parent->left)
    {
        travelNode = travelNode->parent;
    }
    return travelNode->parent;
}


//后继结点（中序）
//若果有右子树：node->right->left->left....
//如果没有右子树呢?
static BalanceBinarySearchTreeNode  * BalanceBinarySearchTreeNodeGetSuccessor(BalanceBinarySearchTreeNode * node)
{
    BalanceBinarySearchTreeNode * travelNode = NULL;
    if(node->right != NULL)
    {
        travelNode = node->right;
        while(travelNode->left != NULL)
        {
            travelNode = travelNode->left;
        }
        return travelNode;
    }

    //程序到这说明没有右子树，右子树为空。，要往上面走

    travelNode = node;
    while(travelNode->parent != NULL && travelNode== travelNode->parent->right)
    {
        travelNode = travelNode->parent;
    }
    return travelNode->parent;
}


/* 结点的度为2 */
static int BalanceBinarySearchTreeNodeHasTwoChildrens(BalanceBinarySearchTreeNode *node)
{
    return node->left != NULL && node->right != NULL;
}

/* 结点的度为1 */
static int BalanceBinarySearchTreeNodeHasOneChildrens(BalanceBinarySearchTreeNode *node)
{
    return (node->left != NULL && node->right == NULL) || (node->left == NULL && node->right != NULL);
}

/* 结点的度为0 (叶子结点) */
static int BalanceBinarySearchTreeNodeIsLeaf(BalanceBinarySearchTreeNode *node)
{
    return node->left == NULL && node->right == NULL;
}



/* 平衡二叉搜索树结点平衡因子(结点才有) */
static int BalanceBinarySearchTreeNodeFactor(BalanceBinarySearchTreeNode *node)
{

    int leftHeight = node->left == NULL ? 0 : node->left->height;
    int rightHeight = node->right == NULL ? 0 : node->right->height;
    return leftHeight - rightHeight;
}

/* 判断是否平衡 */
static int BalanceBinarySearchTreeNodeIsBalance(BalanceBinarySearchTreeNode *node)
{
    return abs(BalanceBinarySearchTreeNodeFactor(node)) <= 1;
}

/* 取两数的较大 */
static int tempMax(int val1, int val2)
{
    return val1 - val2 >=0 ? val1 : val2;
}

/* 更新高度 */
static int BalanceBinarySearchTreeNodeUpdataHeight(BalanceBinarySearchTreeNode *node)
{
    int leftHeight = node->left == NULL ? 0 : node->left->height;
    int rightHeight = node->right == NULL ? 0 : node->right->height;
    
    /* 直接更新 */
    node->height = 1 + tmpMax(leftHeight, rightHeight);
   // return 1 + tmpMax(leftHeight, rightHeight);
   return ON_SUCCESS;
   
}


/* 创建二叉搜索树的结点 */
static BalanceBinarySearchTreeNode *createBalanceBinarySearchTreeNode(ELEMENTTYPE data, BalanceBinarySearchTreeNode *parent)
{
    BalanceBinarySearchTreeNode *newNode = (BalanceBinarySearchTreeNode *)malloc(sizeof(BalanceBinarySearchTreeNode) * 1);
    if (newNode == NULL)
    {
        return NULL; //没有静态前置声明
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    newNode->parent = NULL;
    newNode->height = 1;//结点高度，默认为1
    return newNode;
}

/* 树的插入 */
int BalanceBinarySearchTreeInsert(BalanceBinarySearchTree *pTree, ELEMENTTYPE data)
{
    /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    /* 判断是否为空树 */
#if 0
    if (pTree->size == 0)
    {

    }
#else
    if (pTree->root == NULL)
    {
        pTree->root = createBalanceBinarySearchTreeNode(data, NULL);
        if (pTree->root == NULL)
        {
            return MALLOC_ERROR;
        }
        pTree->size++;
        return ON_SUCCESS;
    }
#endif

    /* 程序走到这个地方, 一定不是空树 */
    BalanceBinarySearchTreeNode *travelNode = pTree->root;

    BalanceBinarySearchTreeNode *parentNode = NULL;
    int cmp = 0;
    while (travelNode != NULL)
    {

        parentNode = travelNode;//这就是此循环的目的，为下一步准备
        /* 比较器 */
        cmp = pTree->compareFunc(data, travelNode->data);
        if (cmp < 0)
        {
            travelNode = travelNode->left;
        }
        else if (cmp == 0)
        {
#if 1
            return ON_SUCCESS;
#else
            travelNode->data = data;
#endif
        }
        else if (cmp > 0)
        {
            travelNode = travelNode->right;
        }
    }
    /* 程序执行到这里 travelNode一定为NULL. */
    BalanceBinarySearchTreeNode *newNode = createBalanceBinarySearchTreeNode(data, parentNode);
    if (newNode == NULL)
    {
        return MALLOC_ERROR;
    }

    if (cmp < 0)
    {
        parentNode->left = newNode;
    }
    else if (cmp > 0)
    {
        parentNode->right = newNode;
    }

    /* 树的元素个数加一. */
    (pTree->size)++;//两个加一，一空一不空

    return ON_SUCCESS;
}


/* 前序遍历 */
static int BalanceBinarySearchTreeInnerPreOrder(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * travelNode)
{
    if (travelNode == NULL)
    {
        return ON_SUCCESS;
    }

    /* 根结点 */
    pTree->printFunc(travelNode->data);
    /* 左子树 */
    BalanceBinarySearchTreeInnerPreOrder(pTree, travelNode->left);
    /* 右子树 */
    BalanceBinarySearchTreeInnerPreOrder(pTree, travelNode->right);

    return ON_SUCCESS;
}

/* 树的前序遍历 */
/* 根结点, 左子树, 右子树 */
int BalanceBinarySearchTreePreOrder(BalanceBinarySearchTree *pTree)
{
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    return BalanceBinarySearchTreeInnerPreOrder(pTree, pTree->root);
}


/* 树的中序遍历 */
static int BalanceBinarySearchTreeInnerInOrder(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * travelNode)
{
    if (travelNode == NULL)
    {
        return ON_SUCCESS;
    }

    /* 左子树 */
    BalanceBinarySearchTreeInnerInOrder(pTree, travelNode->left);
    /* 根结点 */
    pTree->printFunc(travelNode->data);
    /* 右子树 */
    BalanceBinarySearchTreeInnerInOrder(pTree, travelNode->right);

    return ON_SUCCESS;
}


/* 树的中序遍历 */
/* 左子树, 根结点, 右子树 */
int BalanceBinarySearchTreeInOrder(BalanceBinarySearchTree *pTree)
{
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    return BalanceBinarySearchTreeInnerInOrder(pTree, pTree->root);
}


/* 树的后序遍历 */
static int BalanceBinarySearchTreeInnerPostOrder(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * travelNode)
{
    if (travelNode == NULL)
    {
        return ON_SUCCESS;
    }

    /* 左子树 */
    BalanceBinarySearchTreeInnerPostOrder(pTree, travelNode->left);
    /* 右子树 */
    BalanceBinarySearchTreeInnerPostOrder(pTree, travelNode->right);
    /* 根结点 */
    pTree->printFunc(travelNode->data);

    return ON_SUCCESS;
}


/* 树的后序遍历 */
/* 左子树, 右子树, 根结点 */
int BalanceBinarySearchTreePostOrder(BalanceBinarySearchTree *pTree)
{
    if (pTree == NULL)
    {
        return NULL_PTR;
    }
    
    return BalanceBinarySearchTreeInnerPostOrder(pTree, pTree->root);
}

/* 树的层序遍历:背 */
int bnarySearchTreeLeveOrder(BalanceBinarySearchTree *pTree)
{
    /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    if (pTree->root == NULL)
    {
        return ON_SUCCESS;
    }

    DoubleLinkListQueue *queue = NULL;
    doubleLinkListQueueInit(&queue);

    //根结点入队
    doubleLinkListQueuePush(queue, pTree->root);

    //判断队列是不是空队列
    BalanceBinarySearchTreeNode *frontVal = NULL;
    while (!doubleLinkListQueueIsEmpty(queue))
    {
        //取出对头元素
        doubleLinkListQueueFront(queue, (void **)&frontVal);
        doubleLinkListQueuePop(queue);

        //打印器
        pTree->printFunc(frontVal->data);

        //左子树入队
        if (frontVal->left != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->left);
        }

        //右子树入队
        if (frontVal->right != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->right);
        }
    }

    //释放队列
    doubleLinkListQueueDestroy(queue);
    return ON_SUCCESS;
}

/* 树的高度 */
int BalanceBinarySearchTreeGetHeight(BalanceBinarySearchTree *pTree, int *pHeight)
{
    //判空
    if (pTree == NULL || pHeight == NULL)
    {
        return NULL_PTR;
    }

    if (pTree->root == NULL)
    {
        //解引用
        *pHeight = 0;
        return ON_SUCCESS;
    }

    //程序到这个地方，根节点一定不NULL，一定有结点
    int height = 0;
    DoubleLinkListQueue *queue = NULL;
    doubleLinkListQueueInit(&queue);

    doubleLinkListQueuePush(queue, pTree->root);
    int levelSize = 1;

    //判断队列是不是空队列
    BalanceBinarySearchTreeNode *frontVal = NULL;
    while (!doubleLinkListQueueIsEmpty(queue))
    {
        //取出对头元素
        doubleLinkListQueueFront(queue, (void **)&frontVal);
        //出队
        doubleLinkListQueuePop(queue);

        // //打印器
        // pTree->printFunc(frontVal->data);

        levelSize--;

        //左子树入队
        if (frontVal->left != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->left);
        }

        //右子树入队
        if (frontVal->right != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->right);
        }

        /* 树的当前层结点遍历结束 */
        if (levelSize == 0)
        {
            height++;
            doubleLinkListQueueGetSize(queue, &levelSize);
        }
    }
    //释放队列
    doubleLinkListQueueDestroy(queue);
    return ON_SUCCESS;

}


/* 销毁；防止内存泄漏 */
int BalanceBinarySearchTreeDestroy(BalanceBinarySearchTree *pTree)
{
    #if 1
     /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    if (pTree->root == NULL)
    {
        return ON_SUCCESS;
    }

    DoubleLinkListQueue *queue = NULL;
    doubleLinkListQueueInit(&queue);

    //根结点入队
    doubleLinkListQueuePush(queue, pTree->root);

    //判断队列是不是空队列
    BalanceBinarySearchTreeNode *frontVal = NULL;
    while (!doubleLinkListQueueIsEmpty(queue))
    {
        //取出对头元素
        doubleLinkListQueueFront(queue, (void **)&frontVal);
        doubleLinkListQueuePop(queue);

        // // 释放结点---打印器
        // pTree->printFunc(frontVal->data);不可在这里，下面还要用

        //左子树入队
        if (frontVal->left != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->left);
        }

        //右子树入队
        if (frontVal->right != NULL)
        {
            doubleLinkListQueuePush(queue, frontVal->right);
        }

        //释放结点
        if (frontVal != NULL)
        {
           free(frontVal);
           frontVal = NULL;
        }
    }

    //释放队列
    doubleLinkListQueueDestroy(queue);
    //释放树
    if(pTree  != NULL)
    {
        free(pTree);
        pTree = NULL;
    }

    return ON_SUCCESS;


    #else
        /*使用中序遍历的方式释放所有的结点 */
    #endif

}

/* 树的删除 */
//左子树最大的值弄过去
/*
是否是根结点
1.如果要删除的结点的度为2
   找到前驱结点，复制结点的值给到当前结点
   删除前驱结点
   前驱结点一定是度为1或0的

2.如果要删除的结点的度为0（叶子结点)：直接删除


/* 树的删除 */
int BalanceBinarySearchTreeDelete(BalanceBinarySearchTree *pTree, ELEMENTTYPE data)
{

    /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    BalanceBinarySearchTreeDeleteNode(pTree, baseAppointValGetBSTreeNode(pTree, data));
    return ON_SUCCESS;

}

/* 指定删除结点 */
static BalanceBinarySearchTreeNode * baseAppointValGetBSTreeNode(BalanceBinarySearchTree *pTree, ELEMENTTYPE data)
{
    /* 判空 */
    /* 程序走到这个地方, 一定不是空树 */
    BalanceBinarySearchTreeNode *travelNode = pTree->root;

    //比较
    int cmp = 0;
    while(travelNode != NULL)
    {
        cmp = pTree->compareFunc(data, travelNode->data);
        if(cmp < 0)
        {
          travelNode  = travelNode ->left;
        }
        else if (cmp == 0)
        {
            return travelNode;//找到了
        }
        else if(cmp > 0)
        {
           travelNode  = travelNode ->right; 
        }
    }
    //退出循环说明不存在，没找到
    return travelNode;

}


static int BalanceBinarySearchTreeDeleteNode(BalanceBinarySearchTree *pTree, BalanceBinarySearchTreeNode * delNode)
{
    int ret = 0;
    if(delNode == NULL)
    {
        return ret;
    }

    /* 度为2 */
    if(BalanceBinarySearchTreeNodeTwoChildrens(delNode))
    {
        /* 获取当前结点的前驱结点 */
        BalanceBinarySearchTreeNode *preNode =  BalanceBinarySearchTreeNodeGetPrecursor(delNode);
        /* 前驱结点的值赋值给当前结点 */
        delNode->data = preNode->data;
        delNode = preNode;//转变了删除方向
    }
    /* 程序到这个地方，说明要删除的结点度为0或1  */

    /* 度为1 */
    BalanceBinarySearchTreeNode  * childNode = delNode->left != NULL ? delNode->left : delNode->right;
    BalanceBinarySearchTreeNode * freeNode = NULL;
    if(childNode != NULL)
    {
        
        childNode->parent = delNode->parent;
        if(delNode->parent == NULL)
        {
            /* 度为1且是根结点 */
            pTree->root = childNode;
            freeNode = delNode;
            // if(delNode != NULL)
            // {
            //     free(delNode);
            //     delNode = NULL;                
            // }           
        }
        else
        {
             if(delNode == delNode->parent->left)
            {
                // /* 删除结点只有左子树 */
                delNode->parent->left = childNode;
                // free(delNode);
                // delNode = NULL;
            }
            else if(delNode == delNode->parent->right)
            {
                ///* 删除结点只有右子树 */
                delNode->parent->right = childNode;
                // free(delNode);
                // delNode = NULL;
            }
            freeNode = delNode;
        }
    }
    else 
    {
        // //如果就就一个,度为且是根结点
        if (delNode->parent == NULL)
        {
            /* 度为0 && 根结点 */
            freeNode = delNode;
          
            /* 根结点置为NULL. */
            pTree->root = NULL;
        }
       else
       {
            //如果就就一个,度为0 && 根结点
            if(delNode == delNode->parent->left)
            {
                delNode->parent->left = NULL;         
            }
            else if(delNode == delNode->parent->right)
            {
                delNode->parent->right = NULL;
            }
            freeNode = delNode; 
       }
    }
    
    //释放堆空间
    if(delNode != NULL)
    {
    free(delNode);
    delNode = NULL;                
    }
    //树的元素个数减一
    (pTree->size)--;
    return ret;
}

/* 树是否存在该元素值 */
int BalanceBinarySearchTreeIsContainVa(BalanceBinarySearchTree *pTree, ELEMENTTYPE data)
{
    /* 判空 */
    if (pTree == NULL)
    {
        return NULL_PTR;
    }

    // BalanceBinarySearchTreeNode *delNode = baseAppointValGetBSTreeNode(pTree, data);
   return (baseAppointValGetBSTreeNode(pTree, data) == NULL ? 0 : 1);

}

//获取树的元素个数
int BalanceBinarySearchTreeGetSize(BalanceBinarySearchTree *pTree, int *pSize)
{
    /* 判空 */
    if (pTree == NULL || pSize == NULL)
    {
        return NULL_PTR;
    }  
    *pSize = pTree->size;
    return ON_SUCCESS;
}



